문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 피보나치 수열 (문단 편집) === 분할 정복을 이용한 알고리즘 [math(\mathcal{O}(\log n) )] === 피보나치 수로 이루어진 2x2 행렬 [math(\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix})]를 생각하자. 이 행렬에 [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix})]를 곱하면, {{{#!wiki style="text-align:center" [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix} \begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = \begin{pmatrix} 1F_{n+1}+1F_n&1F_n+1F_{n-1} \\ 1F_{n+1}+0F_{n}&1F_n+0F_{n-1} \end{pmatrix} = \begin{pmatrix} F_{n+2}&F_{n+1} \\ F_{n+1} &F_{n} \end{pmatrix})] }}} 를 얻는다. 또한 [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix} = \begin{pmatrix} F_{2}&F_{1} \\ F_{1} &F_{0} \end{pmatrix})]이다. 따라서 다음과 같은 일반화된 공식을 얻을 수 있다: {{{#!wiki style="text-align:center" [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix})] }}} [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix})]를 [math(M)]이라고 하자. [math(M)]을 n-1번 거듭제곱하면 [math(F_n)]을 얻을 수 있다. 그러나 단순히 이를 n-1번 곱하는 방식은 [[시간 복잡도]]가 위의 반복문을 이용한 방식과 동일한 [math(\mathcal{O}(n))]이다. 그러나, [math({M}^{n} {M}^{m} = {M}^{n+m})] 라는 점을 이용하면 이를 [math(\mathcal{O}(\log n) )]으로 줄일 수 있다. 모든 양의 정수는, 2의 제곱수들을 각각 한 번 이하로 더하여 만들 수 있다. 이 사실이 [[2진법]]의 작동 배경이며, 어떤 양의 정수의 2진법 표기에서 i번째 자리수가 의미하는 바는, 해당 정수를 만들기 위해 [math(2^i)]를 몇 번 더해야 하는지이다. 예를 들어, 100과 43을 [[2진법]]으로 나타내면 1100100, 101011인데, 이는 [math(100 = 1100100_2 = 1 \times 2^6+1 \times 2^5+0 \times 2^4+0 \times 2^3+1 \times 2^2+0 \times2^1+0 \times 2^0 = 64+32+4)], [math(43 = 101011_2 = 1 \times 2^5+0 \times 2^4+1 \times 2^3+0 \times 2^2+1 \times 2^1+1 \times 2^0 = 32+8+2+1)]임을 의미한다. 이 사실이 시사하는 바는, 어떤 양의 정수 n의 2진법 표현을 알고 있다면, [math(M)]를 2의 제곱수들만큼 제곱하여 얻은 일련의 행렬들[math(\{M^1, M^2, M^4, M^8, M^{16}, M^{2^5}, M^{2^6} ...\})][* [math(M^mM^m=M^{2m})]이므로, [math(M)]을 제곱하여 [math(M^2)]를 얻고, [math(M^2)]를 제곱하여 [math(M^4)]를 얻고, 또 [math(M^4)]를 제곱하여 [math(M^8)]을 얻는 식으로 차례대로 구할 수 있다.]을 하나의 [[단위행렬]]에다가 각각 한 번 혹은 0번 곱하여 [math(M^n)]을 구할 수 있다는 것이다. [* 예를 들어, [br] [math(M^{100} = M^{64}M^{32}M^{4}I)], [br] [math(M^{43} = M^{32}M^{8}M^2M^1I)] [br]이런 식이다.] 이를 이용해, 양의 정수 n을 입력받아 [math(F_n)]을 구하는 다음과 같은 알고리즘을 만들 수 있다: * n-1의 이진법 표기의 각각 자리수들을 역순으로 나열한 배열 binarr을 만든다. [* n-1이 43이라면, 만들어지는 binarr은 {1, 1, 0, 1, 0, 1}이다.] * [math(M^{2^i})]의 값들을 담을 빈 동적 배열 m_powers를 만든 후, 첫 번째 자리에 [math(M)]을 넣는다. * m_powers의 맨 뒤에 m_powers[-1][* 기존의 맨 마지막 원소]의 제곱을 추가하는 작업을, m_powers의 길이가 binarr의 길이와 같아질 때까지 반복한다. 이 작업이 완료되면, binarr[i]는 [math(M^{n-1})]을 만들기 위해 m_powers[i]가 곱해져야 할 지의 여부를 나타내게 된다. * 2x2 단위행렬 final_mat를 만든다. * 정수 i가 0에서 len(binarr)-1이 될 때까지 1만큼 증가시키며, 다음을 반복한다: * 만약 binarr[i] == 1이라면, final_mat에 m_powers[i]를 곱한다. * final_mat[0][0]이 [math(F_n)]이다. {{{#!syntax python from math import log2 def matmul_2x2(a, b): # 2x2 행렬 곱셈 return_mat = [[0, 0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): return_mat[i][j] += a[i][k] * b[k][j] return return_mat def to_reverse_bin(n: int): return_array = [0 for _ in range(int(log2(n))+1)] while n > 0: temp_lg2n = int(log2(n)) return_array[temp_lg2n] += 1 n -= 2 ** temp_lg2n return return_array def fib(n: int): if n == 0: return 0 elif n == 1: return 1 binarr = to_reverse_bin(n-1) # 또는 python의 내장 라이브러리 함수 bin()을 이용하여 # binarr = list(map(int, reversed(bin(n-1)[2:]))) m_powers = [] m_powers.append( [[1, 1], [1, 0]] ) for i in range(1, len(binarr)): m_powers.append(matmul_2x2(m_powers[-1], m_powers[-1])) final_mat = [ [1, 0], [0, 1] ] for i in range(len(binarr)): if binarr[i]: final_mat = matmul_2x2(m_powers[i], final_mat) return final_mat[0][0] if __name__ == "__main__": print(fib(1000000)) }}}저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기